package hot100.logos41To50;

import hot100.datastruct.TreeNode;

import java.util.HashMap;

/**
 * @author logos
 * date 2025/7/14 12:41
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos48 {

    /**
     * 48. 路径总和 III
     * https://leetcode.cn/problems/path-sum-iii/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        private int ans;

        public HashMap<Long, Integer> map = new HashMap<>();

        public int pathSum(TreeNode root, int targetSum) {
            map.put(0L, 1);
            solve(root, targetSum, 0L);
            return ans;
        }

        public void solve(TreeNode root, int targetSum, Long sum) {
            if (root == null) {
                return;
            }
            sum += root.val;
            ans += map.getOrDefault(sum - targetSum, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            solve(root.left, targetSum, sum);
            solve(root.right, targetSum, sum);
            map.put(sum, map.get(sum) - 1);
        }
    }
}
